#ifndef GAMEENGINE_CORE_GRAPH_QUADTREE_H
#define GAMEENGINE_CORE_GRAPH_QUADTREE_H

#include <GameEngine/Core/core_settings.h>

#include <GameEngine/Geometry/Surfaces/box2d.h>
#include <GameEngine/Core/Graph/quadtree_node.h>

#include <vector>

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=====================================================================

//! Class in charge of representing a quad tree
/*!
 *  A quadtree can be used to divide recursively a two-dimensional space into a set
 *  of squares.
 *
 *  A quadtree is templated by two parameters: E represents the type of elements
 *  stored by the quadtree and T represents the level of numerical precision required
 *  for space subdivision (T would typically either be of type float or double).
 */
template <class E, class T>
class Quadtree {

public:
	//! Typedef used to handle indexes in the vector of quadtree elements
	typedef unsigned int QuadtreeIndex;

	//! Typedef used to handle numbers of quadtree elements
	typedef unsigned int ElementCount;

	//! Typedef used to handle quadtree nodes
	typedef QuadtreeNode<QuadtreeIndex,T> Node;

public:
	Quadtree(int max_depth = 3);
	Quadtree(const Box2d<T>& box, int max_depth = 3);
	Quadtree(const Quadtree& rhs);
	~Quadtree();
	Quadtree& operator=(const Quadtree& rhs);

	const std::vector<E>& elements() const;
	std::vector<E>& elements();

	bool add_element(const E& element, const Point2d<T>& location, bool unique = true);
	bool add_element(const E& element, const Box2d<T>& location, bool unique = true);
	ElementCount remove_element(const E& element);
	bool find_element(const E& element) const;

	bool simplify(ElementCount nb_elements = 10);

	//! Accessor to the main node of the quadtree (read only)
	/*!
	 @return A constant reference to the main node of the quadtree
	 */
	const Node& node() const { return node_; }

	const Node* get_node(const Point2d<T>& location) const;
	Node* get_node(const Point2d<T>& location);
	std::list< const Node* > get_nodes(const Box2d<T>& location,
		QuadtreeNodeItr::QuadtreeNodeItrType type = QuadtreeNodeItr::LowLevelNodes) const;
	std::list< Node* > get_nodes(const Box2d<T>& location,
		QuadtreeNodeItr::QuadtreeNodeItrType type = QuadtreeNodeItr::LowLevelNodes);

protected:
	static bool simplify(Node& node, ElementCount nb_elements);
	static bool subdivide(Node& node, int level);

protected:
	//! The top-level quadtree node
	Node node_;

	//! Elements handled by the quadtree
	std::vector<E> elements_;
};

//=====================================================================

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#include <GameEngine/Core/Graph/quadtree.hpp>

#endif
